All the problems are in minimization here, i.e. if an objective function \(z(x)\) is actually in maximisation, we will minimise \(-z(x)\) instead. Only binary variables are considered here.
The first purpose of this study is to learn how some components of the branch and bound influences the behaviour of the algorithm it terms of computational time (expressed in seconds everywhere) and in term of number of nodes explored (i.e. how much nodes are developed in the branch and bound tree before the algorithm ends).
The branch and bound algorithm will always use the linear relaxation as lower bound set and the incumbent set as upper bound set. At each nodes, the extreme points of the lower bound set are checked for integrality and possibly added to the upper bound set. The components that will vary are:
the node selection : in the multi-objective branch and bound literature, depth first strategies are (almost) always used and are considered as better strategies than breadth first. However, our conjecture is that if a problem with an “easy” single-objective version is solved, then many non-dominated points may be found in a node close to the root node, in the early stages of the tree. Hence, using a breadth first strategy may provide a better upper bound set earlier in the algorithm, as a larger number of points are expected to be found shallow in the tree while only a few points can be found at each node deep in the tree (1 maximum at a leaf node for example). However, it is not clear to see what is the actual impact. Hence, here comes the first research question : how does depth and breadth first strategies affects the behaviour of the algorithm ? (computational time, number of nodes explored)
the variable selection : to the best of our knowledge, no extensive study for variable selection has been conducted in the literature. Sometimes, this component is even not mentioned. As it is not the main purpose of this study, only two rules that rely on the caracteristics of the lower bound set will be tested here.
mof : Most Often Fractional. The branching is operated on the variable that is the most often fractional among the extreme points of the lower bound set.
mfavg : Most Fractional in AVeraGe. The branching is operated on the variable such that its average value among the extreme points of the lower bound set is the most fractional, i.e. the closest to 0.5.
the branching scheme : in a regular branch and bound, branching is operated (i.e. sub-problems are created) in the decision space. In the bi-objective case, it has been shown that creating additional sub-problems in the objective space (procedure called objective branching in this study) leads to better computational times. A new research question arises here : what is the impact of objective branching on a branch and bound algorithm for solving problems with three objectives ? In order to address that, three versions of the branch and bound will be tested (with the best node and variable selection previously identified for each problem configuration):
None : no objective branching is performed. Hence, this version is just a regular branch and bound.
exact : objective branching is performed using the algorithm from [master thesis paper].
unique cone : a unique sub-problem is created at each node. In this case, objective branching is applied on the nadir point of the local upper bounds dominated by the lower bound set. See [master thesis paper] for more details.
The second purpose of this study is to learn how the caracteristics of an instance can affect its difficulty. The difficulty will be here mesured by the size of the non-dominated set, and the computational time required to solve the instance. The computational time will be determined using the branch and bound algorithm previously described. Note that the complexity of an objective space search algorithm is positively correlated to the size of the non-dominated set as the more non-dominated there are, the more integer programs have to be solved.
The focus will be here on the objective function coefficients. The first research question here is: does the range of the objective function coefficient has an impact on the difficulty of the problem ?. In order to answer that, three different ranges will be tested:
For the facility location problems, two sets of costs (i.e. coefficients of objective function) can be identified: the assignment costs (\(c_{ij}\)) and the facility opening costs (\(f_j\)). It is reasonable to assume that these two sets of costs may not take their values in the same range. Let the assignment costs take their values in \([a,b]\), the generation of the facility opening costs will be divided into two categories of instances:
The second research question related to that topic is: does the method used to generate the coefficients of the objective function has an impact on the difficulty of the problem ?. Indeed, the usual procedure to generate objective function is to generate the coefficients randomly in a given range \([a,b]\). However, one could imagine other way to generate coefficient. Four methods will be studied here.
You must enable Javascript to view this page properly.
You must enable Javascript to view this page properly.
You must enable Javascript to view this page properly.
You must enable Javascript to view this page properly.
List of test instances.
Several methods for generating the coefficient of the objective functions are tested here. This is given by the column coef.
Here are tested different combinations of variable and node selection for the basic branch and bound. In the following :
The coefficient are generated using the random method.
The coefficient of the objective functions are in the range [1,10].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1,1000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1000,2000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient are generated using the spheredown method.
The coefficient of the objective functions are in the range [1,10].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1,1000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1000,2000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient are generated using the sphereup method.
The coefficient of the objective functions are in the range [1,10].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1,1000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1000,2000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient are generated using the random method.
The coefficient of the objective functions are in the range [1,10].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1,1000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The coefficient of the objective functions are in the range [1000,2000].
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
In this section, relations between |YN| and various characteristics of the coefficient of the objective function are studied.
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
end